\chapter{本章算法}
\large{\songti{本章将从算法概述、算法核心细节及其他算法实现细节这三个方面介绍本文算法。
		算法概述部分重点分析虚拟纹理实现过程中的问题，然后详细阐述本文算法解决这些问
		题的基本思路及难点。算法核心细节部分重点介绍本文算法核心部分的实现细节。其他
		算法实现细节部分简要介绍本文算法非核心部分的实现细节。
}}
\section{算法概述}
\subsection{问题分析}
实现虚拟纹理的难点在于纹理页的可见性判断和纹理数据的动态加载。
\par 判断哪些纹理页可见的依据有：当前页是否出现在视野中，当前需要采用的mipmap层次。但是在代码中并不能直接得到上述有关信息，只能在片段着色器中计算得到。
\par 当确定了在下一帧之前需要激活哪些页，我们需要将纹理数据载入GPU。但是这里需要的图像数据是将图像分块后的部分图像，因此生成离散图像数据与mipmap也是要处理的问题。
\subsection{本文算法基本思想}
 判断页的可见性的基本思想是：由于渲染管线中对输入顶点的裁剪过程，被输入到片段着色器中的片段其坐标都是在屏幕范围之内的。只要我们能够计算出当前片段属于哪一页，并且记录在缓冲中，就可以在下一帧获取页的可见性信息并进行管理了。为了计算当前片段属于哪一页，除了纹理坐标，还需要当前片段应采样的mipmap层次，可以在着色器程序中使用textureQueryLod函数来获取LOD信息。但我们还需要将着色器中计算得到的可见页序列返回给主程序，以在下一帧之前填充数据。
\par Vulkan中的位块传输指令vkCmdBlitImage可以用于分割图片与生成mipmap。
该指令可将源图像的某一区域的数据复制到目标图像的某一区域，在这个过程中，可以对图像数据执行缩放和过滤操作。我们可以通过第0层的纹理图像生成每一个虚拟纹理页的图像数据，难点在于vkCmdBlitImage参数的计算。
\newpage
\subsection{本文算法流程}
\begin{figure}[h]
	\centering
	\includegraphics[height=0.7\textheight]{Figures/flowchart.png}
\end{figure}
\begin{center}
图1：本文算法流程图
\end{center}
\par 为了实现虚拟纹理，并将虚拟纹理封装为实验室Vulkan渲染框架支持的功能，本文解决思路是将虚拟纹理实现所要求的纹理分页管理交由一个类来实现（CSparseImageWrapper）。该类继承渲染框架中的图像包装类（CImageWrapper），它是对纹理图像功能的封装，用于简化使用纹理的过程。
\par 在程序开始时，输入纹理图像路径创建CSparseImageWrapper类的实例对象，该类对象在进行初始化时，负责获取显卡对稀疏资源支持的有关信息，并根据输入的纹理图像参数进行分页操作。划分页这一部分较为简单，只要设置了每一页的大小，即可推算出每一页的具体信息。划分页后，进行稀疏资源绑定，即根据划分的每一页的大小和位置将显存对象与图像对象绑定。之后将该实例对象用作纹理。
\par 在第一次渲染时，所有纹理页都不包含数据，因此我们在渲染开始前载入一个较底层的mipmap包含的页，保证有纹理可以被采样。
\par 每一次渲染，都会在着色器中计算出当前想要采样哪一页，由于每一帧之间变化相差不大，可以视为下一帧要采样的页和当前想要采样的页相同。
\par 然后便可以根据计算出的可见信息，调用CSparseImageWrapper类提供的函数，填充数据。
对于不再用到的页，也需要释放其占用的显存，以达到使用虚拟纹理的目的。
\section{算法核心细节}
\subsection{位块传输参数计算}
\begin{figure}[h]
	\centering
	\includegraphics[width=\textwidth]{Figures/VkBlitParameter.png}
\end{figure}
\begin{center}
	图2：生成纹理页数据示意图
\end{center}
\quad\quad 如图2所示，现已有作为纹理mipmap第0层的原始图像数据，需要用其红圈所示区域的数据生成下一mipmap层某一纹理页的数据。
\par \textbf{已知参数如下：}
\par \( x_{dst} \) \quad\quad 目的纹理页左上角x坐标
\par \( y_{dst} \) \quad\quad 目的纹理页左上角y坐标
\par \( level \) \quad\, 目的纹理页所处mipmap层次（从第0层开始）
\par \( size_{dst} \) \ \, 目的纹理页大小（纹理页划分为方形，宽度=长度）    
\par \textbf{说明：}以上参数在创建虚拟纹理类实例时已经通过计算得到，详细计算过程将在其他算法实现细节中给出。 ~\\
\par \textbf{要求得的参数及算法为：}
\par 红圈区域左上角x和y坐标：
\[ x_{src}=x_{dst} \cdot 2^{level} \]
\[ y_{src}=y_{dst} \cdot 2^{level} \]
\par 红圈区域大小：
\[ size_{src}=size_{dst} \cdot 2^{level}\] 
\par 在着色器中计算得到可见页的序号后，即可调用CSparseImageWrapper类的成员函数fillPages(uint32\_t vPageCount, uint32\_t vPageIndices)。该函数首先为纹理页分配显存，然后计算参数，通过VkBlitImage命令将红圈区域的图像数据传输到目的页的存储区域，在传输过程中通过过滤（线性过滤或临近过滤），生成缩放的图像。除了数据的加载，这一步骤实际上也是生成mipmap的过程，这避免了提前生成mipmap的存储开销。
\subsection{可见页的序号计算}
在片段着色器中计算当前片段属于哪一页的伪代码如下：
\begin{enumerate}
\item{获取当前片段应采样的mipmap层次： 
\begin{center}
	LOD = textureQueryLod(Texture,TexCoord).y
\end{center}
\textbf{说明：}textureQueryLod用于计算从哪一LOD层次对该纹理进行采样，其返回数组的x成员分量表示要采样的图层，y成员分量表示要采样的LOD层次。textureQueryLod是在GLSL 4.0版本开始得到支持，在一些低端显卡中无法使用。
}
\item{计算从第0层到第LOD - 1层的纹理页总数量pageCount：}\\
int pageCount = 0; \\
int pageCountWidth = TextureWidth / pageSize ; \\
int pageCountHeight t= TextureHeight / pageSize ; \\
for ( int i = 0 ; i < Lod ; i ++)
\{ \\
	pageCount += pageCountWidth * pageCountHeigh ; \\
	pageCountWidth = pageCountWidth / 2 ; \\
	pageCountHeight = pageCountHeight / 2 ; 
\item{该页的序号 = 该页在LOD层的序号 + pageCount：} \\
	pageOffset = int ( float ( pageCountHeight ) * TexCoord.y ) * pageCountWidth \\ +  int ( float ( pageCountWidth ) * TexCoord.x ) + pageCount ;
\end{enumerate}

\subsection{使用缓冲传递可见性信息}
着色器程序是由GPU执行的，为了将页的可见性信息传递回主程序，需要将页的可见性信息储存在缓冲中，与缓冲绑定的显存对象（VkDeviceMemory)不仅对GPU可见，也需要对CPU可见。本项目需要的显存对象性能标志（ propertyFlags）如下：
\par VK\_MEMORY\_PROPERTY\_HOST\_VISIBLE\_BIT：指定该显存可以被映射到内存，以便被CPU访问。
\par VK\_MEMORY\_PROPERTY\_HOST\_COHERENT\_BIT： 保证显存中储存内容和映射的内存信息的一致性。
\par VK\_MEMORY\_PROPERTY\_HOST\_CACHED\_BIT：指定该显存会被缓存在主机上，主机内存对缓存内存的访问要比对非缓存内存的访问快。 ~\\
\par \textbf{使用缓冲传递可见性信息的步骤如下:}
\begin{enumerate}
\item{创建缓冲对象。}
\item{分配上述类型的显存对象,将其与缓冲对象绑定。}
\item{将显存对象映射到CPU可以访问的内存中，记录映射后的内存地址。}
\item{开始渲染循环，着色器程序计算页的可见性信息并记录在缓冲中。}
\item{在下一帧开始之前，对映射后的内存地址进行取值操作，得到可见页序列。}
\end{enumerate}
\newpage
\section{其他算法实现细节}
\subsection{性能优化}
\large{\songti {记录页的可见性信息的缓冲可视作一个初始赋值为0的数组，其长度为总页数，将其某元素赋值为1，就代表其索引对应的页为可见页。主程序只需遍历该数组即可得到可见性信息。}}
\par 当纹理图片很大时，在分页粒度不变的情况下，纹理页的数量会变得很多，上述做法便会影响渲染效率。计算着色器能够基于GPU实现并行计算，从而提高计算能力。因此，本算法使用计算着色器进行可见性信息的处理，处理流程如下。
\begin{figure}[h]
	\centering
	\includegraphics[height=0.5\textheight]{Figures/computeShader.png}
\end{figure}
\begin{center}
	图3：可见性信息处理流程图
\end{center}
\newpage
\subsubsection{3.3.1.1 ClearPageCounts.computeShader}
\textbf{主要代码如下:} \\
uint PageCounts[2]; \\
void main() \\
\{ 
\par if ( gl\_GlobalInvocationID.x  <  2 )  PageCounts[ gl\_GlobalInvocationID.x ] = 0; \\
\}
\par PageCounts数组有两个分量，分别表示可见页的数量与将要移除页的数量，该计算着色器负责在每一次循环时将数组赋值为0。
\subsubsection{3.3.1.2 ProgressVisibility.computeShader}
\textbf{主要代码如下:} \\
uint PageCounts[2]; \quad //记录可见页的数量与将要移除页的数量 \\ 
uint PageTable[]; \quad //记录由片段着色器计算出的页的可见性信息 \\
uint AlivePageTable[]; \quad //记录可见页序列 \\
uint RemovePageTable[]; \quad //记录将要移除的页序列 \\
uint PrePageTable[]; \quad // 记录上一帧的可见页序列，用于在下一帧计算要移除的页\\
void main() \\
\{ 
\par uint Index = gl\_GlobalInvocationID.x; 
\par if ( PageTable[Index] == 1 ) 
\par \{ 
\par uint currentTexureID = atomicAdd ( PageCounts[0] , 1 ); 
\par AlivePageTable[currentTexureID] = Index; 
\par \} 
\par else if( PrePageTable[Index] == 1 )
\par \{ 
\par uint currentTexureID = atomicAdd ( PageCounts[1], 1 ); 
\par  RemovePageTable[currentTexureID] = Index; 
\par  \} 
\par PrePageTable[Index] = PageTable[Index]; 
\par PageTable[Index] = 0; \\
\}
\par 经过计算着色器的处理，我们由PgaeTable数组得到了可见页序列和要移除的页序列，并且分别得到呢它们的数量，主程序便可通过缓冲得到这些信息，进行纹理页的更新。
\section{采样算法}
\textbf{片段着色器中的采样方法如下：}
\begin{enumerate}
	\item{通过textureQueryLod计算从哪一LOD层次对该纹理进行采样。}
	\item{将LOD作为输入参数，使用sparseTextureClampARB进行纹理采样，该函数会返回纹理采样结果，可判断当前LOD层是否有纹理数据驻留。}
	\item{若在LOD层采样成功，则结束采样，否则用LOD+1继续采样，直到采样成功。}
\end{enumerate}
\section{分页算法}
\textbf{CSparseImageWrapper类实例对象初始化时，执行的分页操作算法为：}
\begin{enumerate}
	\item{查询当前显卡对稀疏图像的相关支持信息，VkSparseImageMemoryRequirements，其包含了纹理页的划分粒度信息(VkExtent3D imageGranularity)。}
	\item{根据纹理图像大小计算总共有多少mipmap层：
		\begin{center}
			NumLevel = floor ( log2 ( max ( WidthBase , HeightBase )) + 1 )
		\end{center}
	}
	\item{计算每一mipmap层的纹理页在其mipmap层所处位置并记录。}
	
\end{enumerate}





